package com.algorithm.learning.base.图;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/29 22:54
 **/
public class Dijkstra算法 {

    /**
     * Dijkstra算法要解决的问题：
     *
     * 给一个出发点，求这个点到各个点的最短距离
     *
     * Dijkstra算法的核心就是：要构建一张最小距离表，记录每个节点到其他点的最短距离！！！
     * 要注意：Dijkstra算法要求边的权值一定是正数，如果有负数，那么如果图有环的话，那么最短距离可能就是负无穷大了，所以不能用Dijkstra算法
     *
     * 1、Dijkstra算法必须要指定一个源点
     *
     * 2、生成一个源点到各个点的最小距离表，一开始只有一条记录，即源点到自己的最小距离为0，源点到其他点的最小距离都为正无穷大
     *
     * 3、从距离表中拿出没有拿过记录里的最小记录，通过这个点发出的边，更新源点到各个点的最小距离表，不断重复
     *
     * 4、源点到所有点记录如果都被拿过一遍，过程停止，最小距离表得到
     *
     * 具体算法逻辑，参考图：<p>[Dijkstra算法解析图](img/Dijkstra算法解析图)</p>
     * @param from
     * @return
     */
    public static Map<Node, Integer> dijkstra1(Node from) {
        /*
            从head出发到所有点的最小距离
            key: 从head出发到达的点T
            value: 从head出发到达点T的最小距离
            如果在表中，没有T的记录，则表示 从head出发到T这个点的距离为正无穷
         */
        Map<Node, Integer> distanceMap = new HashMap<>();
        // 到自己的点距离为0
        distanceMap.put(from, 0);
        // 已经求过距离的点，存在selectedNodes，以后再也不碰
        Set<Node> selectedNodes = new HashSet<>();

        // 得到最小距离，且这个节点没有被求过距离的点
        // 一开始一定是from自己
        Node minNode = getMinDistanceAndUnSelectedNode(distanceMap, selectedNodes);
        while (minNode != null) {
            int distance = distanceMap.get(minNode);
            // 遍历当前点的所有边
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                // distanceMap中没有toNode，表示当前点到toNode的距离是正无穷，那么此时更新这个节点的最小距离
                // 就是当前距离distance+当前边的大小edge.weight
                if (!distanceMap.containsKey(toNode)) {
                    distanceMap.put(toNode, distance + edge.weight);
                } else {
                    // 如果找到toNode，那就表示toNode已经在最小距离表里了，这里就判断哪个距离更小，就更新
                    distanceMap.put(toNode, Math.min(distanceMap.get(toNode), distance + edge.weight));
                }
            }
            // 锁住当前的minNode, 之后就不能用了
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnSelectedNode(distanceMap, selectedNodes);
        }
        return distanceMap;
    }

    /**
     * 之前没有被选过点，并且找到distanceMap找到最小距离
     *
     * @param distanceMap
     * @param selectedNodes
     * @return
     */
    private static Node getMinDistanceAndUnSelectedNode(Map<Node, Integer> distanceMap, Set<Node> selectedNodes) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            Node node = entry.getKey();
            int distance = entry.getValue();
            // 这里的目的，就是为了找到当前点到其他点目前的最小距离
            if (!selectedNodes.contains(node) && distance < minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }
}
